1. Technical Field of the Invention
The present invention relates to an integrated circuit and method for performing modulo mathematical calculations. In particular, the present invention relates to an integrated circuit that performs modulo exponentiation mathematics with binary numbers.
2. Description of Related Art
Many public-key encryption algorithms, like the RSA encryption and decryption system or the Diffie-Hellman key exchange system, are based on the mathematical operation of modulo exponentiation. This operation can be described as follows: EQU c=M.sup.k mod n.
In other words, to compute c, raise M to the power of k and divide it by n, then save the remainder of the division instead of the quotient. In a typical RSA calculation, M would be the clear text message to be signed, k would be the private key, n would be the public key (the modulus), and c would be the ciphertext.
Modulo calculations, or synonymously, modular calculations, can be performed by electronic equipment. As the exponent, k, and the ciphertext, M, and size of n increases, the modulo calculations become time and power consuming to the electronic circuits. Generally, computation time depends on the size of n and the value of k. In hardware, circuits that implement modulo mathematics, n and k also provide an indication of the amount of power consumed by the circuit while performing the operation.
As mentioned above, n is publicly known as a public key, but k could be a private key that should be kept secret in order to maintain the integrity of the encryption system. In order to calculate c, it is useful to break the modulo exponentiation up into a multiple of simple operations. Usually, the modulo exponentiation is split up into a series of modulo-square and modulo-multiplication operations. "Modulo" in this context means division by the modulus while saving the remainder of the operation. Consider C=M.sup.17 mod n for example: EQU c=M.sup.17 mod n=((((1*M mod n).sup.2 mod n).sup.2 mod n).sup.2 mod n).sup.2 *M mod n
To determine c, first calculate the modulo-multiplication of 1 and M. The result is then modulo-squared four times respectively until we get M.sup.16 mod n. Then modulo-multiply this result by M to get M.sup.17 mod n.
When modulo mathematics is performed in circuitry on an integrated circuit, the math is generally performed using binary numbers. Taking a closer look at the exponent in the above example, in binary notation, 17 would be (10001). Looking at the bits from most significant (MSB) to least significant (LSB),i.e., from left to right, and performing the modulo math described above, notice that each time a 1 is encountered then a modulo-square is performed with the intermediate result, which is initialized to a 1, and then a modulo-multiply with M is performed. When a 0 is encountered only a modulo-square is performed on the intermediate result to get the next intermediate result. Thus, depending on whether a 1 or a 0 was present in a position in the private key, k exponent, it may take different amounts of time to calculate the next intermediate result.
Thus, cryptosystems often take different amounts of time to process different inputs. For example, if a system uses the same secret exponent, k, for multiple Diffie-Hellman exchanges or RSA encryptions, the exponent can often be determined by an "attack" of monitoring timing aspects of the circuitry which performs the calculations. The attacker may first observe a plurality operations while measuring the time (t) taken to compute each c=M.sup.k mod n.
According to Paul C. Kocher in his paper, Kocher, CRYPTOANALYSIS OF DIFFIE-HELLMAN, RSA, DSS, AND OTHER SYSTEMS USING TIMING ATTACKS, Dec. 7, 1995, the attack is simplest to understand in an extreme case. Suppose the circuitry can perform a modulo-multiplication extremely fast, but takes a relatively long time to perform both a modulo-square and a modulo-multiply calculation. An attacker can determine the exponent bits by monitoring the calculation process. The bits in the exponent that are 1's will calculate slowly in comparison to the exponent bits that are 0's.
In actual practice, modular exponentiation implementations do not usually have such extreme timing characteristics, but do have enough variation for the attack to work. Furthermore, the total time of the calculation of the whole exponent can also be determined which adds an ability to statistically determine the maximum number of 1's and 0's possible if the modulo calculation time for each 1 and 0 is known.
Another "attack" available to an attacker or pirate is to monitor the power requirements of the integrated circuit. Generally, the modulo math calculation of a modulo-multiply and a modulo-square will each require a different amount of energy when implemented in either hardware or firmware in an integrated circuit. An attacker could monitor the power consumption of an integrated circuit and in a fashion similar to the timing attack determining the exponent k. A "1" will require more power than a 0 to compute a modular exponentiation calculation.
Of course, if possible, both attacks could be performed together thereby potentially increasing the speed at which an attacker could determine the exponent, k, private key.
It would be advantageous to have an integrated circuit that could thwart both the timing attack and/or the power monitoring attack described above.